package deom1;

public class Test1 {

    public class ListNode {
        int val;
        ListNode next = null;

        ListNode(int val) {
            this.val = val;
        }
    }

    public class PalindromeList {
        public boolean chkPalindrome(ListNode A) {
            // write code here
            ListNode fast = A;
            ListNode slow = A;
            ListNode head = A;
            while (fast != null && fast.next != null) {
                fast = fast.next.next;
                slow = slow.next;
            }
            ListNode ret = slow.next;
            while (ret != null) {
                ListNode retN = ret.next;
                ret.next = slow;
                slow = ret;
                ret = retN;
            }
            while (head != slow) {
                if (head.val != slow.val) {
                    return false;
                }
                if (head.next == slow) {
                    return true;
                }
                head = head.next;
                slow = slow.next;
            }
            return true;
        }
    }

}
